iT邦幫忙

2022 iThome 鐵人賽

DAY 25
0
自我挑戰組

Udemy課程上完你也可以開始Codewars 30天系列 第 25

[Day25] Codewars >>> Decimal to Factorial and Back (Python)

  • 分享至 

  • xImage
  •  

題目(5kyu):

Coding decimal numbers with factorials is a way of writing out numbers in a base system >that depends on factorials, rather than powers of numbers.

In this system, the last digit is always 0 and is in base 0!. The digit before that is >either 0 or 1 and is in base 1!. The digit before that is either 0, 1, or 2 and is in >base 2!, etc. More generally, the nth-to-last digit is always 0, 1, 2, ..., n and is in >base n!.

Read more about it at: http://en.wikipedia.org/wiki/Factorial_number_system

Example
The decimal number 463 is encoded as "341010", because
463 = 3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0!

If we are limited to digits 0..9, the biggest number we can encode is 10!-1 (= >3628799). So we extend 0..9 with letters A..Z. With these 36 digits we can now encode >numbers up to 36!-1 (= 3.72 × 1041)

Task
We will need two functions. The first one will receive a decimal number and return a >string with the factorial representation.

The second one will receive a string with a factorial representation and produce the >decimal representation.

Given numbers will always be positive.

解題思路

題目理解:設計兩個函式,能將數字以階乘數系統的形式作轉換。
故463轉換後會得到"341010",如下:
463 = 3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0!

另題目要求將A~Z也代入擴展,意即最大可表達的數為37!-1。 (10個數字加上26字母故最高可表達位數是36!)
故:371993326789901217467999448150835199999999 = "ZYXWVUTSRQPONMLKJIHGFEDCBA9876543210"
可利用math.factorial()輔助解題如下:

import math

#將所有階乘位數的字元,依序建立成字串供後續輸出時調用
all_digit = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def biggest_digit(num):
    "找出一個數字轉換為階乘數系統後,將其最大的階乘位數&係數以(d ,m)形式返還"
    #依序檢驗 d! 與 num的關係
    for d in range(1,37):
        #若 d!大於num,代表其最大位數為(d-1)!
        if math.factorial(d)>num:
            #再依序檢驗其係數m乘上(d-1)!後與num的關係即可得知m,須留意m的最大範圍為d本身(詳見階乘數系統關於基數之說明)
            for m in range(1,d+1):
                if math.factorial(d-1)*m >num:
                    return (d-1,m-1)
                elif math.factorial(d-1)*m == num:
                    return (d-1,m)
        #若d!洽等於num則代表:num = d! * 1 ,故直接返還(d , 1)
        elif math.factorial(d) == num:
            return (d,1)

def dec_2_fact_string(nb):
    """將數字nb以階乘數系統方式表達"""
    lst = []
    dic = {}
    number = nb
    reslut = ""
    #不斷找number其最大階乘位數&係數,找到後就將number減去 digtl! * multiplier,直到number不足0
    while number > 0:
        digit,multiplier= biggest_digit(number)
        #將(digtl,multiplier)存入lst備用
        lst.append((digit,multiplier))
        number -= math.factorial(digit)*multiplier
    #將lst中的每個元組,以digit為key,multiplier為值存入
    for digit,multiplier in lst:
        dic[digit] = all_digit[multiplier]
    #lst中的第一個元組的digtl會是整個nb的最大位數,故從最大位數開始往下檢查看每個位數是否有出現在dic.keys()中
    for i in range(lst[0][0],0,-1):
        #若有則代表有對應的multiplier
        if i in dic.keys():
            reslut += str(dic[i])
        #若無代表該位數上multiplier為0
        else: reslut+="0"
    #最後結果須再補上最小位數 0!*0 
    return reslut+"0"

def fact_string_2_dec(string):
    """將以階乘數系統表達的字串轉換成十進位數字"""
    reslut = 0
    for m in range(1,len(string)+1):
        digit_ind = string[-m]
        #digit_ind在all_digit中的索引值即為其代表的階乘位數
        reslut += math.factorial(m-1)*int(all_digit.index(digit_ind))
    return reslut

上一篇
[Day24] Codewars >>> Split Strings (Python)
下一篇
[Day26] Codewars >>> Pete, the baker (Python)
系列文
Udemy課程上完你也可以開始Codewars 30天30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言